// https://leetcode.cn/problems/find-pivot-index/description/

// 算法思路总结：
// 1. 前缀和+后缀和寻找数组中心下标
// 2. 中心下标定义：左侧所有元素和等于右侧所有元素和
// 3. 预处理：prev[i]表示前i个元素和，next[i]表示后i个元素和
// 4. 遍历检查：prev[i-1] == next[i+1]时找到中心下标
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    static const int N = 10010;
    int prev[N], next[N];

    int pivotIndex(vector<int>& nums) 
    {
        int m = nums.size();
        memset(prev, 0, sizeof(prev));
        memset(next, 0, sizeof(next));

        for (int i = 1 ; i <= m ; i++)
        {
            prev[i] = prev[i - 1] + nums[i - 1];
            next[m - i + 1] = next[m - i + 2] + nums[m - i];
        }

        for (int i = 1 ; i <= m ; i++)
        {
            if (prev[i - 1] == next[i + 1])
                return i - 1;
        }

        return -1;
    }
};

int main()
{
    vector<int> nums1 = {1, 7, 3, 6, 5, 6}, nums2 = {1, 2, 3};
    Solution sol;

    cout << sol.pivotIndex(nums1) << endl;
    cout << sol.pivotIndex(nums2) << endl;

    return 0;
}